import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;


public class DeepFirst {
    private static class TreeNode {
        int data;
        TreeNode leftChild;
        TreeNode rightChild;

        TreeNode(int data) {
            this.data = data;
        }
    }
    /**
     * create binary tree
     * @param inputList array binary tree
     * @return linked list binary tree
     */
    public static TreeNode createBinaryTree(LinkedList<Integer> inputList) {
        TreeNode node = null;
        if (inputList == null || inputList.isEmpty()) {
            return null;
        }
        Integer data = inputList.removeFirst();
        if (data != null) {
            node = new TreeNode(data);
            node.leftChild = createBinaryTree(inputList);
            node.rightChild = createBinaryTree(inputList);
        }
        return node;
    }
    /* root -> left -> right */
    public static void preOrderTraveral(TreeNode node) {
        if (node == null) {
            return;
        }
        System.out.println(node.data);
        preOrderTraveral(node.leftChild);
        preOrderTraveral(node.rightChild);
    }
    /* left -> root -> right */
    public static void inOrderTraveral(TreeNode node) {
        if (node == null) {
            return;
        }
        inOrderTraveral(node.leftChild);
        System.out.println(node.data);
        inOrderTraveral(node.rightChild);
    }
    /* left -> right -> root */
    public static void postOrderTraveral(TreeNode node) {
        if (node == null) {
            return;
        }
        postOrderTraveral(node.leftChild);
        postOrderTraveral(node.rightChild);
        System.out.println(node.data);
    }

    public static void preOrderTraveralWithStack(TreeNode root){
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode treeNode = root;
        while(treeNode != null || !stack.isEmpty()){
            while (treeNode != null) {
                System.out.println(treeNode.data);
                stack.push(treeNode);
                treeNode = treeNode.leftChild;
            }
            if (!stack.isEmpty()) {
                treeNode = stack.pop();
                treeNode = treeNode.rightChild;
            }
        }
    }
    public static void inOrderTraveralWithStack(TreeNode root){
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode treeNode = root;
        while(treeNode != null || !stack.isEmpty()){
            while (treeNode != null) {
                stack.push(treeNode);
                treeNode = treeNode.leftChild;
            }
            if (!stack.isEmpty()) {
                treeNode = stack.pop();
                System.out.print(treeNode.data);
                treeNode = treeNode.rightChild;
            }
        }
    }
    public static void postOrderTraveralWithStack(TreeNode root){
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode treeNode = root;
        // ...
        TreeNode last = null;
        while (treeNode != null || !stack.isEmpty()) { // while循环保证进栈顺序：根 -> 左
            while (treeNode != null) {
                stack.push(treeNode);
                treeNode = treeNode.leftChild;
            }
            treeNode = stack.peek(); // 回溯到根
            if (treeNode.rightChild == null || treeNode.rightChild == last) { // 右没有；或者从右上来的
                System.out.println(treeNode.data);
                stack.pop(); // 出栈，下次就能回溯到根
                last = treeNode;
                treeNode = null;
            } else {
                treeNode = treeNode.rightChild; // 流转到右，右作为新的根
            }
        }
    }
    // 根进栈 -> 左进栈... -> 左出栈 -> 回溯到根 -> 找到右 -> 右进栈 -> (如果有左，左进栈...) -> 右出栈

    // 广度优先，层序遍历，利用LinkedList队列（链表）
    public static void levelOrderTraveral(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root); // 链表尾添加，返回boolean
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll(); // 链表头删除并返回第一个元素
            System.out.println(node.data);
            if (node.leftChild != null) {
                queue.offer(node.leftChild);
            }
            if (node.rightChild != null) {
                queue.offer(node.rightChild);
            }
        }
    }

    // 广度优先，层序遍历，利用递归
    public static int depth(TreeNode root) {
        if (root == null) return 0;
        int left = depth(root.leftChild);
        int right = depth(root.rightChild);
        if (left >= right) {
            return left + 1;
        } else {
            return right + 1;
        }
    }
    public static void orderByRecursion(TreeNode root, int level) {
        TreeNode treeNode = root;
        if (treeNode == null || level < 1) {
            return;
        }
        if (level == 1) {
            System.out.println(treeNode.data);
        }
        orderByRecursion(treeNode.leftChild, level - 1); 
        orderByRecursion(treeNode.rightChild, level - 1); 
    }
    public static void levelOrderTraveralWidthRecursion(TreeNode root) {
        TreeNode treeNode = root;
        if (treeNode == null) {
            return;
        }
        int depth = depth(treeNode);
        for (int i = 1; i <= depth; i++) {
            orderByRecursion(treeNode, i);
        }
    }
      
    public static void main(String[] args) {
        // LinkedList<Integer> inputList = new LinkedList<Integer>(Arrays.asList(new Integer[]{3,2,9,null,null,10,null,null,8,null,4}));
        LinkedList<Integer> inputList = new LinkedList<Integer>(Arrays.asList(new Integer[]{1,2,4,null,null,5,null,null,3,null,6,null,null}));
        TreeNode treeNode = createBinaryTree(inputList);
        // System.out.print("pre");
        // preOrderTraveral(treeNode);
        // System.out.print("in");
        // inOrderTraveral(treeNode);
        // System.out.print("post");
        // postOrderTraveral(treeNode);
        System.out.print("stack pre \n");
        preOrderTraveralWithStack(treeNode);
        System.out.print("stack in \n");
        inOrderTraveralWithStack(treeNode);
        System.out.print("stack post \n");
        postOrderTraveralWithStack(treeNode);

        System.out.println("linkedList level order \n");
        levelOrderTraveral(treeNode);

        System.out.println("depth: " + depth(treeNode));

        System.out.println("level order resursion \n");
        levelOrderTraveralWidthRecursion(treeNode); 
        
    }
}